package sort;

import java.util.Arrays;

/*
        冒泡排序:比较相邻数组中的元素,前者大于后者,交换顺序,每一轮都会找出一个最大的数放在数组尾部
                    n个元素排序,复杂度O(n^2)
        选择排序:从0号元素开始,依次与后面的元素比较,大于后者则交换,每一轮都找出一个最小的数放在数组头部
                    n个元素排序,复杂的O(n^2)
        二分查找:每次比较中间元素与目标元素大小,指针指向新的中间位置
 */
public class Sort {
    public static void main(String[] args) {
        int[] arr = {10, 16, 20, 13, 35, 31};
//      bubbleSort(arr);
        selectSort(arr);
        int target = 110;
        int midIndex = getaIndex(arr, target);
        if (midIndex == -1) {
            System.out.println("查无此数");
        } else
            System.out.println(Arrays.toString(arr) + " " + midIndex);

        /**使用异或,交换数据
         int a=3,b=4;
         a=a^b;
         b=a^b;
         a=a^b;
         System.out.println(a+" "+b);
         */
    }
        //二分查找
    private static int getaIndex(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;
        int midIndex;
        while (start <= end) {
            midIndex = (start + end) / 2;
            if (target == arr[midIndex]) {
                return midIndex;
            } else if (target > arr[midIndex]) {
                start = midIndex + 1;
            } else if (target < arr[midIndex]) {
                end = midIndex - 1;
            }
        }
        return -1;
    }
        //选择排序
        private static void selectSort ( int[] arr){
            for (int i = 0; i < arr.length - 1; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    if (arr[i] > arr[j]) {
                        int temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
        }

        //冒泡排序
        private static void bubbleSort ( int[] arr){
            for (int i = 0; i < arr.length - 1; i++) {
                for (int j = 0; j < arr.length - 1 - i; j++) {
                    if (arr[j] > arr[j + 1]) {
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
        }



}